package com.leetcode.algorithm.topic;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 平衡二叉树相关算法题解
 * (done)110. 平衡二叉树
 * (done)108. 将有序数组转换为二叉搜索树
 * @author: jie.deng
 * @time: 2019年3月27日 上午10:23:48
 */
public class AvlTreeSolution {
	
    /**
     * 110. 平衡二叉树
     * 
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 
     * 本题中，一棵高度平衡二叉树定义为：
     * 
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     * 
     * 示例 1:
     * 
     * 给定二叉树 [3,9,20,null,null,15,7]
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回 true 。
     * 
     * 示例 2:
     * 
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     * 
     *        1
     *       / \
     *      2   2
     *     / \
     *    3   3
     *   / \
     *  4   4
     * 返回 false 。
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        int h = getHeight(root);
        return h != -1;
    }

    /**
     * 若平衡二叉树,返回树的高度；若非平衡二叉树，返回-1。
     * @param root
     * @return
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int hl = getHeight(root.left);
        int hr = getHeight(root.right);
        if (hl == -1 || hr == -1 || Math.abs(hl - hr) > 1) {
            return -1;
        }
        return Math.max(hl, hr) + 1;
    }
    

    /**
     * 108. 将有序数组转换为二叉搜索树
     * 
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     * 
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     * 
     * 示例:
     * 
     * 给定有序数组: [-10,-3,0,5,9],
     * 
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     * 
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     * 
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }

    private TreeNode sortedArrayToBST(int[] nums, int fromIdx, int toIdx) {
        if (fromIdx >= toIdx) {
            return null;
        }
        int mid = (fromIdx + toIdx - 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, fromIdx, mid);
        root.right = sortedArrayToBST(nums, mid + 1, toIdx);
        return root;
    }
}